/*
https://leetcode.cn/problems/count-unreachable-pairs-of-nodes-in-an-undirected-graph/description/
2316.统计无向图中无法互相到达点对数
方钊堉 2024.10.13
并查集
*/

class Solution {
public:
    int parent[100010]; // 并查集的父节点数组
    bool visited[100010]; // 标记是否已经访问过某个节点

    // 查找函数，带路径压缩优化
    int findParent(int x) {
        if (parent[x] != x) {
            parent[x] = findParent(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 计算无向图中的连通分量之间的点对数目
    long long countPairs(int n, vector<vector<int>>& edges) {
        vector<int> size(n, 1); // 每个节点初始时都是一个独立的连通分量，大小为1
        for (int i = 0; i < n; i++) {
            parent[i] = i; // 初始化每个节点的父节点为其自身
            visited[i] = false; // 初始化访问标记数组
        }

        // 处理所有边，进行合并操作
        for (const auto& edge : edges) {
            int u = edge[0], v = edge[1];
            int pu = findParent(u), pv = findParent(v);
            if (pu != pv) { // 如果两个节点不在同一个连通分量中
                size[pv] += size[pu]; // 更新较大连通分量的大小
                parent[pu] = pv; // 合并两个连通分量
            }
        }

        long long result = 0, total = 0;
        vector<int> componentSizes; // 存储每个连通分量的大小

        // 统计每个连通分量的大小，并标记已处理过的连通分量
        for (int i = 0; i < n; i++) {
            int pi = findParent(i);
            if (!visited[pi]) {
                visited[pi] = true; // 标记该连通分量已被处理
                total += size[pi]; // 累加连通分量大小
                componentSizes.push_back(size[pi]); // 存储连通分量大小
            }
        }

        // 计算不同连通分量之间的点对数目
        for (int i = 0; i < componentSizes.size(); i++) {
            result += (total - componentSizes[i]) * componentSizes[i]; // 计算点对数目
        }

        return result / 2; // 因为每对点被计算两次，所以结果需要除以2
    }
};